import java.lang.reflect.Array;
import java.util.Arrays;

public class TextHeap {
    public int[] elem;
    public int usedSize;

    public TextHeap() {
        this.elem = new int[10];
    }

    public void siftDown(int parent, int usedSize) {
        int child = parent * 2 + 1;   //必是左孩子


        while (child < usedSize) {   //父结点有左孩子就继续循环
            //右孩子存在并且比左孩子小的话，把标记给右孩子
            if (child + 1 < usedSize && elem[child + 1] < elem[child]) {
                child = child + 1;
            }

            if (elem[parent] < elem[child]) {
                break;  //已经满足小根堆的性质
            } else {
                swap_elem(child, parent);

                parent = child;
                child = child * 2 + 1;
            }
        }
    }

    public void initElem(int[] array) {
        for (int i = 0; i < array.length; i++) {
            elem[i] = array[i];
            usedSize++;
        }
    }

    public void createHeap() {
        //parent = 4,3,2,1,0
        //将标记定位到最后一棵子树
        for (int parent = (usedSize - 2) / 2; parent >= 0; parent--) {
            siftDown(parent, usedSize);
        }
    }

    public void swap_elem(int a, int b) {
        int tmp = elem[a];
        elem[a] = elem[b];
        elem[b] = tmp;
    }

    public void push(int a) {
        if (usedSize >= elem.length) {
            elem = Arrays.copyOf(elem, elem.length * 2);
        }
        //没满
        this.elem[usedSize] = a;
        siftUp(usedSize);

        usedSize++;
    }

    public void siftUp(int child) {
        //向上调整
        int parent = (child - 1) / 2;
        while (child > 0) {
            if (elem[parent] < elem[child]) {
                break;
            } else {
                swap_elem(parent, child);
                child = parent;
                parent = (child - 1) / 2;
            }
        }
    }

    public int pop() {
        if (empty()) {
            return -1;
        }

        int del_val = elem[0];
        swap_elem(0, usedSize - 1);
        usedSize--;
        siftDown(0, usedSize - 1);
        return del_val;
    }

    public boolean empty() {
        return usedSize == 0;
    }


    //堆排序：按照从小到大的顺序应该建立大根堆，start和end交换之后一直更新大根堆
    public void heap_sort() {
        int end = usedSize - 1;

        while (end > 0) {  //直到最大的那个数字重新回到堆顶的额时候结束循环
            swap_elem(0, end);
            siftDown(0, end);
            end--;
        }
    }
}
